home *** CD-ROM | disk | FTP | other *** search
/ BMUG Revelations / BMUG Revelations.toast / Entertainment / Strategy / FaultyTowers Of Hanio v2.0 / FaultyTowers Of Hanio v2.0.rsrc / TEXT_146.txt < prev    next >
Text File  |  1989-07-27  |  3KB  |  42 lines
  1. By choosing the Player... item under the Execution Menu you can have the computer solve the puzzle for you.  There are two choices for algorithms, recursive or iterative. 
  2.  
  3. Towers of Hanoi is a classic example of a problem that can be solved quite simply using recursion.  If you want to move n disks from tower X to tower Z, first move n-1 disks from X to Y, then move the bottom disk from X to Z. Finish by moving the n-1 disks from Y to Z. The following is the recursive algorithm used by this program to solve the puzzle.
  4.  
  5.           procedure MoveDisks(x,y,z:tower; NumberOfDisks:integer);
  6.           {move NumberOfDisks from top of x to z, y is intermediate}
  7.           begin
  8.               if NumberOfDisks=1 then
  9.                   MoveTopDisk(x,z)       
  10.               else
  11.                   begin
  12.                       MoveDisks(x,z,y, NumberOfDisks-1);
  13.                       MoveTopDisk(x,z);
  14.                       MoveDisks(y,x,z, NumberOfDisks-1);
  15.                   end;
  16.           end;
  17.  
  18. It is quite easy to prove that the recursive algorithm works (use induction).  The following iterative algorithm is quite simple looking but it is more difficult to prove.  There seems to be some controversy about who should get credit for the algorithm. In his book: The TURING OMNIBUS, A.K. Dewdney attributes it to Buneman and Levy who published it in 1980.  Martin Gardner's book Mathematical Puzzles and Diversions  was first published in 1959 and it contains an iterative algorithm that is very similar.  
  19.  
  20. Putting the controversy behind us, here is the main idea. Think of the towers as arranged in a triangle.
  21.  
  22.          y
  23.  
  24.       x     z
  25.  
  26. Always move the smallest disk clockwise, after each move of the small disk make the only other move that does not involve the smallest disk.  In Faulty Towers of Hanoi the procedure moves clockwise if the total number of disks is even, counter-clockwise for an odd total.  
  27.  
  28. In pseudo code:
  29.  
  30.   procedure SolveTowerOfHanoi(NumberOfDisks);
  31.   {move the disks from x to z}
  32.  
  33.   begin
  34.      if NumberOfDisks even then
  35.         Move smallest disk clockwise one tower
  36.         Make only other possible move not using the smallest disk
  37.      else
  38.         Move smallest disk counter-clockwise one tower
  39.         Make only other possible move not using the smallest disk
  40.   end;
  41.            
  42. There is a bug that occurs if you have the computer solving the puzzle using the iterative method and the RPN box is checked in the Disks dialog. You might enjoy trying to figure out why the recursive procedure works but the iterative method does funny things.